const MAX_LOAD_FACTOR = 0.75;
const MIN_LOAD_FACTOR = 0.25;
export function hashFunc(str, max) {
    // 1.定义hashCode
    let hashCode = 0;
    // 2.霍纳算法
    for (let i = 0; i < str.length; i++) {
        // 31可以为任何质素, charCodeAt获取‌ASCII码
        hashCode = 31 * hashCode + str.charCodeAt(i)
    }
    // 映射下标值
    hashCode = hashCode % max;
    return hashCode;
}
// 判断一个数是否为质数
// 性能低的版本:效率低
export function isPrime1(num) {
    if (typeof num != "number") throw new Error('请输入正确的数字')
    // 质数也称为素数，它表示大于1的自然数中，
    for (let i = 2; i < num; i++) {
        // 只能被1和自己整除的数
        if (num % i === 0) return false;
    }
    return true;
}
// 进阶版
export function isPrime(num) {
    if (typeof num != "number") throw new Error('请输入正确的数字')
    // 获取num平方根
    let temp = Math.ceil(Math.sqrt(num))
    // 质数也称为素数，它表示大于1的自然数中，
    for (let i = 2; i <= temp; i++) {
        // 只能被1和自己整除的数
        if (num % i === 0) return false;
    }
    return true;
}

export class HashTable {
    constructor() {
        this.storage = []; // 数组存放元素
        this.count = 0; // 当前存放多少个元素
        this.limit = 7; // 总个数(多少个一层数组)
    }
    // 哈希函数
    hashFunc(str, max) {
        // 1.定义hashCode
        let hashCode = 0;
        // 2.霍纳算法
        for (let i = 0; i < str.length; i++) {
            // 31可以为任何质素, charCodeAt获取‌ASCII码
            hashCode = 31 * hashCode + str.charCodeAt(i)
        }
        hashCode = hashCode % max;
        return hashCode;
    }
    // 放入/修改元素
    put(key, value) {
        // 1.根据key映射到index
        const index = hashFunc(key, this.limit)
        // 2.取出数组
        let bucket = this.storage[index];
        if (bucket === undefined) {
            // 如果没有第二层数组就创造一个
            bucket = [];
            this.storage[index] = bucket;
        }
        // 3.判断是插入还是修改
        let overide = false;
        for (let i = 0; i < bucket.length; i++) {
            const tuple = bucket[i];
            // 为修改
            if (tuple[0] === key) {
                tuple[1] = value;
                overide = true;
            }
        }
        // 4.如果没有覆盖，那么就是新增
        if (!overide) {
            bucket.push([key, value]);
            this.count++;
            // 如果二层数组的个数大于一层数组的0.75倍
            if (this.count > this.limit * MAX_LOAD_FACTOR) {
                // 就扩容
                let minList = this.limit * 2
                minList = this.getPrime(minList)
                this.resize(minList)
            }
        }
    }
    // get：根据传入的key获取元素value
    get(key) {
        // 1.根据key获取index（外层数组的）
        const index = hashFunc(key, this.limit)
        // 2.获取bucket(第二层数组)
        const bucket = this.storage[index]
        if (!bucket) return null
        for (let i = 0; i < bucket.length; i++) {
            const tuple = bucket[i]; // key，value数组
            if (tuple[0] == key) {
                return tuple[1]
            }
        }
        return null
    }
    // remove：根据key删除元素
    remove(key) {
        // 根据key获取index
        const index = hashFunc(key, this.limit);
        // 根据index找到bucket
        const bucket = this.storage[index];
        // 如果没有找到就不用删除并且返回null；
        if (!bucket) return null
        // 反之，找到了元素删除并且返回它
        for (let i = 0; i < bucket.length; i++) {
            const tuple = bucket[i];
            if (tuple[0] == key) {
                bucket.splice(i, 1)
                this.count--
                // 如果一层数组的个数大于8并且二层数组小于一层数组的0.25倍
                if (this.limit > 8 && this.count < this.limit * MIN_LOAD_FACTOR) {
                    // 就缩小容量
                    let minList = Math.floor(this.limit / 2)
                    minList = this.getPrime(minList)
                    this.resize(minList)
                }
                return tuple[1]
            }
        }
    }
    // isEmpty()：如果哈希表中不包含任何元素，返回true，如果哈希表长度大于0则返回false
    isEmpty() {
        return this.count === 0;
    }
    // size()：返回哈希表包含的元素个数。与数组的length属性类似
    size() {
        return this.count
    }
    // resize()：扩容或者缩小容量
    resize(newLimit) {
        if (!newLimit) throw new Error('请输入总个数')
        // 1.保存旧的数组内容
        let oldStorage = this.storage;
        // 2.重置属性
        this.limit = newLimit;
        this.storage = [];
        this.count = 0;
        // 3.取出oldStorage所有的元素,重新放入到storage中
        for (const bucket of oldStorage) {
            if (!bucket) continue;
            for (const tuple of bucket) {
                this.put(tuple[0], tuple[1])
            }
        }
    }
    // 判断是否是质数
    isPrime(num) {
        if (typeof num != "number") throw new Error('请输入正确的数字')
        // 获取num平方根
        let temp = Math.ceil(Math.sqrt(num))
        // 质数也称为素数，它表示大于1的自然数中，
        for (let i = 2; i <= temp; i++) {
            // 只能被1和自己整除的数
            if (num % i === 0) return false;
        }
        return true;
    }
    // 获取一个质数
    getPrime(num) {
        let newNum = num;
        // 当传入值不是质数就继续往上+,直到是质数为止
        while (!isPrime(newNum)) {
            newNum++;
        }
        return newNum;
    }
}